For transmissions and storages of digital signals such as satellite communications, mobile communications, optical disks, and the like, reduction in required electric power, reduction in the size of antenna, improvements in the transmission speed (or storage capacitance), and the like are required at all times. In order to satisfy such demands, error correction coding techniques having a large coding gain are being employed. Among those, the low-density-parity-check (referred to as LDPC code hereinafter) is known as the error correction code having a large coding gain, and it is being employed more and more into the above-described various kinds digital communication systems and storage devices.
The coding device utilizing the LDPC code generates a block inspection matrix of a quasi-cyclic LDPC code, and transfers it to a coder. The coder performs coding processing on an input message that is a digital signal by utilizing the inspection matrix to generate a code word, and outputs it to a modulator. The modulator transmits it to a transmission path such as an optical fiber via a carrier wave. Alternatively, the transmission path may be replaced with a storage medium such as an optical disk.
Note here that the LDPC code not only means a single error correction coding system but is used as a general term for error correction codes having such a characteristic that the inspection matrix is sparse (most of the components in the matrix is 0, and the number of components of 1 is small). Among those, the quasi-cyclic LDPC code can constitute an error coding system having a large coding gain through using a repeat decoding method such as a sum-product algorithm or a min-sum algorithm. This will be described in more details hereinafter.
Expression 1 shows an r×n block matrix (r and n are natural numbers satisfying r≦n, and k=n−r), which shows a block inspection matrix of a quasi-cyclic LDPC code. In the cyclic permutation matrix as each of the components of the block matrix shown in Expression 1, the degree u(i, j) shows an integer between 0 and m−1 (m is an integer of 1 or larger) or a symbol −∞ (i is an integer between 0 and r−1, and j is an integer between 0 and n−1).
Further, Expression 2 shows an m×m cyclic permutation matrix P shown in Expression 1. P is a permutation matrix in which one each of “1” exists in each row and each column, and other components are “0”. Further, each row vector of P is cyclic-shifted to the right from the row vector of the upper stage thereof. Only the first component of the row vector of the highest stage is “1”, and the other components are “0” (the component at the far left end is considered as the 0th component).
When u is an integer between 0 and m−1, “P^u” shows a cyclic permutation matrix in which only the u-th component of the highest row vector is “1” and other components are “0”. Here, “u” is called as the degree of the cyclic permutation matrix P^u. When the degree u is “0”, P^u is a unit matrix in which only the diagonal component is “1”. Thus, this is particularly expressed as “1”. Further, in order to simplify the notation, the cyclic permutation matrix P^−∞ of the degree −∞ is to show a zero matrix in which all the components are “0”.
Incidentally, “A with a superscript B (e.g., A to the power of B) is expressed as “A^B”, and “A with a subscript B” is expressed as “A^B” in the lines other than numerical expressions.
                    (                                                            P                                  u                  ⁡                                      (                                          0                      ,                      0                                        )                                                                                                      P                                  u                  ⁡                                      (                                          0                      ,                      1                                        )                                                                                      …                                                      P                                  u                  ⁡                                      (                                          0                      ,                                              k                        -                        1                                                              )                                                                                      …                                                      P                                  u                  ⁡                                      (                                          0                      ,                                              n                        -                        1                                                              )                                                                                                                          P                                  u                  ⁡                                      (                                          1                      ,                      0                                        )                                                                                                      P                                  u                  ⁡                                      (                                          1                      ,                      1                                        )                                                                                      …                                                      P                                  u                  ⁡                                      (                                          1                      ,                                              k                        -                        1                                                              )                                                                                      …                                                      P                                  u                  ⁡                                      (                                          1                      ,                                              n                        -                        1                                                              )                                                                                                          …                                      …                                      …                                      …                                      …                                      …                                                                          P                                  u                  ⁡                                      (                                                                  r                        -                        1                                            ,                      0                                        )                                                                                                      P                                  u                  ⁡                                      (                                                                  r                        -                        1                                            ,                      1                                        )                                                                                      …                                                      P                                  u                  ⁡                                      (                                                                  r                        -                        1                                            ,                                              k                        -                        1                                                              )                                                                                      …                                                      P                                  u                  ⁡                                      (                                                                  r                        -                        1                                            ,                                              n                        -                        1                                                              )                                                                                      )                            (                  Expression          ⁢                                          ⁢          1                )                                                          ⁢                  P          =                      (                                                                                                                                                    1                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              1                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              …                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              …                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              1                                                                              1                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              )                                              (                  Expression          ⁢                                          ⁢          2                )            
The code length of the quasi-cyclic LDPC code having the block matrix in a form of Expression 1 as the inspection matrix is n×m bits. Among the bit series of the m×m bits, a series whose matrix product with Expression 1 becomes zero is considered as a set of transmission bit string. On the reception side, it is judged whether or not there is an error in the reception bit string depending on whether or not the matrix product of the reception bit string and the inspection matrix of Expression 1 is zero. When there is an error, decoding processing for correcting the error is performed by using the inspection matrix with the use of the sum-product or min-sum algorithm mentioned above.
Through the above processing, the quasi-cyclic LDPC code having the inspection matrix shown in Expression 1 is determined depending on how each degree u(i, j) is to be selected regarding each (i, j). For determining the degree u(i, j), three points, i.e., the error correction capability is high, the coding processing can be performed easily, and the storage capacity required for holding the values of each of the degrees u(i, j) is small, can be taken as the guidelines for determining the degree u(i, j). The technical subject to be overcome is to provide a determining method of the degrees u(i, j) that satisfy the three points and to provide an efficient and economic coding device of the LDPC code having the inspection matrix defined according to the determined degrees u(i, j).
Among those, the error correction capability as the first guideline is known to depend on the weight distribution regarding the row and column blocks of the inspection matrix and the number of short-length cycles. The weight distribution c(w) regarding the row block shows, regarding a positive integer w, the number of row blocks i where the number of column blocks j satisfying u(i, j)≠−∞ matches w (i is an integer between 0 and r−1, j is an integer between 0 and n−1). The weight distribution v(w) regarding the column block shows the number of column blocks j where the number of column blocks i satisfying u(i, j)≠−∞ matches w.
It is known that the weight distributions v(w) and c(w) desired in terms of the error correction capability can be calculated by density evolution and the like. Further, the cycle of the inspection matrix means a closed path formed by branches connecting between vertexes by having “1” in the components of the inspection matrix as the vertexes. The number of branches in the cycle shows the length of the cycle.
FIG. 11 is an explanatory chart showing an example of the cycle (closed path) in the inspection matrix. In FIG. 11, a cycle 801 of length 4 and a cycle 802 of length 6 are illustrated. In a case of utilizing the sum-product or min-sum algorithm described above, it is considered a condition for achieving a high error correction capability not to have a short cycle of equal to or less than the length 4 such as the cycle 801. That is, regarding the error correction capability as the first guideline, it is necessary to take not only the weight distribution but also the number of short cycles into consideration.
As a technique for overcoming the above-described technical subject, there is a method shown in Non-Patent Document 3. This technique defines the degrees u(i, j) as in Expression 3 (1 is an integer satisfying 0<1<r−1) regarding the column block j where j≧k (k shows n−r).
                              u          ⁡                      (                          i              ,              j                        )                          =                  {                                                    0                                                                                  when                    ⁢                                                                                  ⁢                    j                                    =                                      i                    +                    k                    +                    1                                                                                                                        b                  i                                                                                                  when                    ⁢                                                                                  ⁢                    j                                    =                                      i                    +                    k                                                                                                      x                                                                                  when                    ⁢                                                                                  ⁢                    j                                    =                                                            k                      ⁢                                                                                          ⁢                      and                      ⁢                                                                                          ⁢                      i                                        =                                          r                      -                      1                                                                                                                          y                                                                                  when                    ⁢                                                                                  ⁢                    j                                    =                                                            k                      ⁢                                                                                          ⁢                      and                      ⁢                                                                                          ⁢                      i                                        =                    ℓ                                                                                                                        -                  ∞                                                                              other                  ⁢                                                                          ⁢                  than                  ⁢                                                                          ⁢                  above                  ⁢                                                                          ⁢                  cases                                                                                        (                  Expression          ⁢                                          ⁢          3                )                                (                                                            P                                  u                  ⁡                                      (                                          0                      ,                      0                                        )                                                                                                      P                                  u                  ⁡                                      (                                          0                      ,                      1                                        )                                                                                      …                                      …                                                      P                                  u                  ⁡                                      (                                          0                      ,                                              k                        -                        1                                                              )                                                                                                      P                                  b                  0                                                                    I                                                                                                                                                                                                                                                                                                                      0                                                                          P                                  u                  ⁡                                      (                                          1                      ,                      0                                        )                                                                                                      P                                  u                  ⁡                                      (                                          1                      ,                      1                                        )                                                                                      …                                      …                                                      P                                  u                  ⁡                                      (                                          1                      ,                                              k                        -                        1                                                              )                                                                                      0                                                      P                                  b                  1                                                                    I                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              …                                                                                                                          P                                  b                  2                                                                    …                                                                                                                                                                                                                                                                      …                                      …                                                                                                                                                                              …                                                      P                y                                                                                                                                                                                            …                                      …                                                                                                                                                                                                  …                                      …                                                                                                                                                                              …                                      …                                                                                                                                                                                                                                                  …                                      I                                                                                                                                                                                                                                                                                                                                                                                                                                                                                  0                                                                                                                                                                                                                                                                                                                                      P                                  b                                      r                    -                    2                                                                                      I                                                                          P                                  u                  ⁡                                      (                                                                  r                        -                        1                                            ,                      0                                        )                                                                                                      P                                  u                  ⁡                                      (                                                                  r                        -                        1                                            ,                      1                                        )                                                                                      …                                      …                                                      P                                  u                  ⁡                                      (                                                                  r                        -                        1                                            ,                                              n                        -                        1                                                              )                                                                                                      P                x                                                    0                                                                                                                                                                                                                                                                                                                                      P                                  b                                      r                    -                    1                                                                                      )                            (                  Expression          ⁢                                          ⁢          4                )            
In Expression 3 and Expression 4, degrees b—0, b—1, - - - , b_r1, x are defined to be able to easily employ the coding method depicted in Non-Patent Document 4. For the values regarding the degrees u(i, j) of 0≦i<r, 0≦j<k other than the above, it is first judged whether or not u(i, j)=−∞. Then, the value of u(i, j) is determined regarding (i, j) that satisfies u(i, j)≠−∞.
FIG. 12 is a flowchart showing an example of the determining method of u(i, j) according to the techniques depicted in Non-Patent Documents 3 and 4. In the processing shown in FIG. 12, first, b—0, b—1, - - - , b_r1, x, and y are determined (step S901), and the weight distribution c(w) regarding the row block and the weight distribution v(w) regarding the column block of the inspection matrix are determined (w is an integer). Subsequently, the weight distributions v(w) and c(w) are calculated (step S902), and the row and column blocks i and j satisfying u(i, j)≠−∞ are determined according to the weight distributions (step S903).
The row and column blocks are not necessarily determined uniquely. Further, as described above, all the blocks according to the weight distributions calculated in step S902 do not necessarily have a high error correction capability. This is taken into consideration in general, and the row and column blocks i and j satisfying u(i, j)≠−∞ are determined successively from those that follow the same weight distributions by using random numbers while paying attention to the number of short cycles.
Through the processing up to step S903, whether or not all u(i, j) are −∞ can be determined. Subsequently, the column blocks are selected successively from the one with the smallest weight (step S904), and the numerical value of u(i, j*) regarding the selected column block j* is determined in such a manner that the number of the shot cycles of the matrix of Expression 4 becomes smaller (step S905). The processing of steps S904 to 905 is repeated until all u(i, j) are determined (step S906). Thereby, the numerical values of u(i, j) are determined successively regarding (i, j) satisfying u(i, j)≠−∞.
There are followings as Patent Documents related to that. Among those, in Patent Document 1, depicted is a technique which decreases the circuit scale of a coding device by performing masking processing on a parity inspection matrix according to a specific rule. In Patent Document 2, depicted is an inspection matrix generating method which acquires a plurality of compound rates with a single inspection matrix by arranging a masked quasi-cyclic matrix and a cyclic permutation matrix at prescribed positions. In Patent Document 3, depicted is a coding/decoding method which performs coding by using a parity check matrix constituted with sub-matrices having a specific regularity in the row and column weights.    Patent Document 1: WO 2007/072721    Patent Document 2: WO 2007/080827    Patent Document 3: Japanese Patent Application Publication 2008-508776    Non-Patent Document 1: RobertGallager, “Low-density-parity-check Codes”, IEEE Transoperations on InformationTheory, January, 1962, pp 21-28    Non-Patent Document 2: D. J. C. Mackay, “Good Error-Correcting Codes Based on very sparse matrices”, IEEE Transoperations on InformationTheory, March, 1999, pp 339-431    Non-Patent Document 3: Myung, Yang, Kim, “Quasi-Cyclic LDPC Codes for Fast Encoding”, IEEE Transoperations on InformationTheory, August, 2005, pp 2894-2901    Patent Document 4: Richardson, Urbanke, “Efficient Encoding of Low-density-parity-check Codes”, IEEE Transoperations on InformationTheory, February, 2001, pp 638-656
In the inspection matrix in a form of Expression 4 determined by the above-described technique, observed between the values of each of the degrees u(i, j) is no regularity but randomness. Thus, it is necessary to have a storage region of (k_r)log(2_m) dimension in order to hold the inspection matrix required in the structure of a coding or decoding device. However, when there is a regularity between the values of each of the degrees u(i, j), the error rate characteristic is deteriorated.
Therefore, many storage regions are required for holding the inspection matrix required in the coding device and the decoding device of the quasi-cyclic LDPC code. In particular, in a communication system which uses a plurality of different LDPC codes of different coding rates, frame lengths, error rate characteristic, and the like according to the factors such as the state of the communication path, there are such issues that still more storage regions are required for holding the inspection matrix and the time required for switching the coding device becomes greater. Patent Documents 1 and 2 are designed to overcome the above-described issues and are effective for reducing the storage region required for using a plurality of LDPC codes. However, there is no special consideration taken for shortening the time required for the switching, so that it does not overcome that point of issue. This point is not considered by the techniques in Patent Document 3 and Non-Patent Documents 1 to 4 either, so that it cannot be overcome by combining those techniques.
An object of the present invention is to provide a coding device, an error-correction code configuration method, and a program thereof, which can reduce the storage region required for using a plurality of low-density-parity-check codes (LDPC) and reduce the time for the switching at the time of using those properly.